package jjn.round1;

import commons.TreeNode;

import java.util.*;

/**
 * @author Jjn
 * @since 2022/9/18 10:00
 */
public class Offer_32_PrintBinaryTreeV3 {

    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            Deque<Integer> level = new LinkedList<>();
            Deque<TreeNode> levelQueue = new LinkedList<>();
            while (queue.peek() != null) {
                TreeNode poll = queue.poll();
                TreeNode left = poll.left;
                TreeNode right = poll.right;
                if (leftToRight) {
                    level.addLast(poll.val);
                } else {
                    level.addFirst(poll.val);
                }
                if (left != null) {
                    levelQueue.add(left);
                }
                if (right != null) {
                    levelQueue.add(right);
                }
            }
            for (TreeNode node : levelQueue) {
                queue.offer(node);
            }
            leftToRight = !leftToRight;
            result.add(new ArrayList<>(level));
        }
        return result;
    }
}
